/*
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。


例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
 

提示：

1 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 仅由大小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<int>> visited(m, vector<int>(n, 0));
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (result) break;
                if (board[i][j] == word[0])
                    dfs(board, i, j, m, n, word, 1, visited);
            }
        }
        return result;
    }
    void dfs(const vector<vector<char>>& board, int x, int y, const int m, const int n, const string& word, int index, vector<vector<int>>& visited) {
        if (index == word.size()) result = true;
        if (result) return;

        visited[x][y] = true;

        for (const vector<int>& dir : dirs) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && board[newX][newY] == word[index] && !visited[newX][newY]) {
                dfs(board, newX, newY, m, n, word, index + 1, visited);
            }
        }
        visited[x][y] = false;
    }
private:
    const vector<vector<int>> dirs = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };
    bool result{false};
};